#include "tree_2_4.h"
#include <iostream>

using namespace std;

Leaf::Leaf ( InnerNode *parent , Tree_2_4 *tree ) : Node ( parent , tree, true )
{
	int i;

	for ( i = 0; i < 4; i++ )
	{
		pointers[i] = NULL;
	}

	next = NULL;
}

void Leaf::Insert ( int studentId, Lesson lesson )
{
	if ( this->Has ( studentId ) )
	{
		/* .. . ........ ....... ... ... ......, ... ......
		 *... ... ...... .. ......... .......
		 */

		int position = FindStudent ( studentId );
		
		LessonList *list = (LessonList *) pointers[position];
		list->AddLesson ( lesson );

		return;
	}
	else if ( this->IsFull() )
	{	
		/* .. .. ..... .... ... ....... ........,
		 *.. .... ... ... ... .... ... ......... .... 
		 *... ......... ......
		 */

		Leaf *newLeaf = new Leaf ( this->parent, tree );
		
		this->Split ( newLeaf, studentId, lesson);
		
		if ( this->HasParent() )
		{
			/*.. ....... ...... ... ...... ... ... .... ........ .....
			 *... ... ......, ... ............ ... ..... ... .......... 
			 *... ... .........
			 */

			parent->Insert ( newLeaf->Max(), newLeaf );
			parent->Insert ( this->Max(), this );
		}
		else
		{
			/*...... .. ... ....... ......, ........ ... ......
			 *.. ........... ... ......... .... ... .....
			 *.......... ...... .. ........ .. Max ids ... ... ......
			 *... ... ....... ... ........ .. .....
			 */

			tree->NewRoot ( this, this->Max(), newLeaf, newLeaf->Max(), true );
			this->parent = ( InnerNode *) tree->root;
			newLeaf->parent = ( InnerNode *) tree->root;
		}
	}
	else
	{
		/* .... ........ ... .......... */
	
		int i, j;

		/* ...... ... ..... ... ...... .. ...........
		 * .. ......... ........ ... .......... ....
		 */
		
		for ( i = 0; i < count; i++ )
		{
			if ( studentId < studentIds[i] )
			{
				for ( j = count; j > i; j-- )
				{
					studentIds[j] = studentIds[j - 1];
					pointers[j] = pointers[j - 1];
				}

				studentIds[i] = studentId;

				pointers[i] = NULL;
				pointers[i] = new LessonList();
				LessonList *list = ( LessonList *)pointers[i];
				list->AddLesson ( lesson );

				count++;
				tree->NewStudentId();

				return;
			}
		}

		/*.. .......... . ......... ........ ... ... .......
		 *.......... .... ... ... .... ... .... .......... */

		studentIds[count] = studentId;

		pointers[count] = NULL;
		pointers[count] = new LessonList();
		LessonList *list = ( LessonList* ) pointers[count];
		list->AddLesson ( lesson );

		count++;
		tree->NewStudentId();

		if ( this->HasParent() )
		{
			InnerNode *parent = ( InnerNode *)this->parent;
			parent->UpdateSeparator ( this, studentId );
		}
	}
}

void Leaf::Split ( Leaf *newLeaf, int studentId, Lesson lesson ) 
{
	int i;		

	newLeaf->pointers[0] = pointers[2];
	pointers[2] = NULL;
	newLeaf->studentIds[0] = studentIds[2];
	newLeaf->pointers[1] = pointers[3];
	pointers[3] = NULL;
	newLeaf->studentIds[1] = studentIds[3];
	
	this->count = newLeaf->count = 2;
	newLeaf->next = this->next;
	this->next = newLeaf;

	/* ........ ... .......... ......... ... ......... ...... */

	Leaf *insertionLeaf;

	/* .......... ... ...... ... ...... .. ....
	 *.. ......... .........
	 */

	studentId > this->Max() ? insertionLeaf = newLeaf : insertionLeaf = this;

	int j;

	/* ...... ... ..... ... ...... .. ...........
	 * .. ......... ........ ... .......... ....
	 */
		
	for ( i = 0; i < insertionLeaf->count; i++ )
	{
		if ( studentId < insertionLeaf->studentIds[i] )
		{
			for ( j = insertionLeaf->count; j > i; j-- )
			{
				insertionLeaf->studentIds[j] = insertionLeaf->studentIds[j - 1];
				insertionLeaf->pointers[j] = insertionLeaf->pointers[j - 1];
			}

			insertionLeaf->studentIds[i] = studentId;

			insertionLeaf->pointers[i] = NULL;
			insertionLeaf->pointers[i] = new LessonList();
			LessonList *list = ( LessonList *) insertionLeaf->pointers[i];
			list->AddLesson ( lesson );

			insertionLeaf->count++;
			insertionLeaf->tree->NewStudentId();

			return;
			}
		}

		/*.. .......... . ......... ........ ... ... .......
		 *.......... .... ... ... .... ... .... .......... */

		insertionLeaf->studentIds[count] = studentId;

		insertionLeaf->pointers[count] = NULL;
		insertionLeaf->pointers[count] = new LessonList();
		LessonList *list = ( LessonList* ) insertionLeaf->pointers[count];
		list->AddLesson ( lesson );

		insertionLeaf->count++;
		insertionLeaf->tree->NewStudentId();

		if ( insertionLeaf->HasParent() )
		{
			parent->UpdateSeparator ( insertionLeaf, studentId  );
		}
}
int Leaf::FindStudent ( int studentId )
{
	int i;

	for ( i = 0; i < count; i++ )
	{
		if ( studentIds[i] == studentId )
		{
			return i;
		}
	}

	return NOTFOUND;
}





LessonList *Leaf::GetLessonList ( int studentId )
{
	int i;

	for ( i = 0; i < count; i++ )
	{
		if ( studentIds[i] == studentId )
		{
			return (LessonList *) pointers[i];
		}
	}

	return NULL;
}

void Leaf::RangePrint ( int from, int to )
{
	Leaf *leaf = this;
	int i = this->Find ( from );

	if ( i == NOTFOUND )
	{
		return;
	}

	do
	{
		LessonList *lessons = ( LessonList * ) leaf->pointers[i];

		cout << leaf->studentIds[i];
		lessons->Print();

		i++;
		
		if ( i == leaf->count)
		{
			leaf = leaf->next;

			if ( leaf == NULL )
			{
				break;
			}

			i = 0;

			continue;
		}
		

	} while ( leaf->studentIds[i] <= to );
}

